/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 邓大帅
 * Date: 2023-02-22
 * Time: 13:58
 */
public class Sort1 {
    // 选择排序
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array, i, minIndex);
        }
    }

    private static void swap(int[] array, int n, int m) {
        int tmp = array[n];
        array[n] = array[m];
        array[m] = tmp;
    }


    // 堆排序
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length-1;
        while (end > 0) {
            swap(array, 0, end);
            downwardAdjustment(array, 0, end);
            end--;
        }
    }

    //以大根堆的方式排序
    private static void createBigHeap(int[] array) {
        //找到最后一个节点的父亲节点
        int parents = (array.length-1-1)/2;
        for (; parents >= 0; parents--) {
            downwardAdjustment(array, parents, array.length);
        }
    }
    //向下调整
    private static void downwardAdjustment(int[] array, int parents, int len) {
        int child = 2*parents+1;
        //至少有左孩子
        while (child < len) {
            //child指向左右孩子最大的那个
            if(child + 1 < len && array[child] < array[child+1]) {
                child++;
            }
            if(array[child] > array[parents]) {
                swap(array, child, parents);
                parents = child;
                child = 2*parents + 1;
            }else {
                break;
            }
        }
    }
}

